1. Field of the Invention
Embodiments of the present invention relate to a system, medium, and method for estimating unknown locations of nodes by use of location information on nodes having known locations in a communication system including the nodes.
2. Description of the Related Art
In a general communication system, data is transmitted and received between a mobile element and a base station. That is, the mobile element and the base station directly transmit and receive data without having to pass through other nodes. In contrast, when data of a certain node is to be transmitted to a base node in an ad-hoc sensor network, other nodes can also be utilized. Referring to FIG. 1, the configuration of the ad-hoc sensor network is described below. The ad-hoc sensor network includes of an operator 100, a base node 102, and a plurality of nodes, as shown in FIG. 1.
The operator 100 requests the base node 102 to collect necessary data. The data requested by the operator 100 may relate to information on temperature of the environment around a sensor field 104, for example. The base node 102 requests the requested data from each node located in the sensor field 104, and forwards the data received from each node to the operator 100. Likewise, each node collects the data requested by the base node 102, and transmits the collected data to the base node 102. Nodes located within a certain distance from the base node 102 transmit the collected data directly to the base node 102. Other nodes located outside of the certain distance from the base node 102 transmit the collected data to the base node 102, via adjacent nodes of the base node 102, not directly to the base node 102, so as to minimize the power consumed for the data transmission. Typically, the distance between the base node 102 to another node is directly proportional to the power consumed by the data transmission between the base node 102 and the other node. Accordingly, nodes outside of the certain distance from the base node 102 transmit their collected data via a plurality of other nodes so as to reduce the power consumption for the data transmission. Hereinbelow, a node relaying data of another node will be referred to as a relay node. The relay node can transmit the collected data directly to the base node 102 or via other relay nodes.
The nodes in the sensor network require and obtain location information of each node to transmit data to the base node 102. By use of the location information, it can be determined whether to transmit the data directly to the base node 102 or via the other nodes, i.e., relay nodes.
The nodes in the sensor network may obtain their locations by way of a global positioning system (GPS), and can then exchange the obtained location information with each other. However, all the nodes in the sensor network may not have GPS, which is high-priced. Thus, some of the nodes in the sensor network have GPS, while the other nodes utilize the location information of the GPS equipped nodes. Specifically, the nodes without GPS may estimate their locations by use of the relative locations from the GPS-equipped nodes. A method for estimating the locations of the non-GPS equipped nodes is described below.
FIG. 2 illustrates nodes in the sensor network. The nodes A1 through A3 are equipped with GPS, and the nodes U1 through U4 are not equipped with GPS. Thus, the nodes A1 through A3 can acquire their locations using the GPS while the nodes U1 through U4 cannot acquire their locations, due to their absence of GPS. The non-GPS equipped nodes can estimate their locations using Sum-dist and DV-hop.
A distance between adjacent nodes can be calculated using power consumption for the data transmission and reception. As noted above, power consumption depends on transmission distance. Typically, the distance between the nodes is directly proportional to the power consumption. The power consumption enables one to calculate the distance between the nodes. For example, it can be assumed that the distance between the nodes A2 and U1 is 6, the distance between the nodes U1 and U5 is 4, and the distance between the nodes U6 and A3 is 5. The distance between the nodes U1 and U6 is 6, and the distance between the nodes U6 and A3 is 5.
The following describes how the distance between remote nodes can be calculated using Sum-dist, particularly, the distance of the node U1 with respect the nodes A1 through A3. The distance between the nodes A1 and U1 is 9 by simply adding the distance 4 between the nodes U1 and U5 and the distance 5 between the nodes U5 and A1. The distance between the nodes A2 and U1 is 6. The distance between the nodes A3 and U1 is estimated to 11 by simply adding the distance 6 between the nodes U1 and U6 and the distance 5 between the nodes U6 and A3.
DV-hop calculates distances between nodes using a hop number between the nodes and an average hop distance. The nodes A1 and A2 know their locations using their GPS, as mentioned above, and can acquire the distance between the nodes A1 and A2 using their location information. For example, it is assumed that the distance between the nodes A1 and A2 is 12. As the hop number between the nodes A1 and A2 is 3, the per-hop distance can be calculated as 4. The hop indicates the transmission unit. Accordingly, the nodes A1 and A2 have three transmission units of the nodes A1 and U5, the nodes U5 and U1, and the nodes U1 and A2. The nodes A1 and U1 have two hops, with a distance of 8 therebetween. The nodes A2 and U1 have one hop, with a distance 4 therebetween. Further, the nodes U1 and A3 have two hops, with a of distance 8.
The conventional methods can calculate the relative distance in such simple manners, but provide inaccurate distances. That is, the conventional methods adds the distances between nodes without considering the topology of the nodes. DV-hop, especially, does not consider that the per-hop distance may differ between different nodes.